package LeetCode刷题;

import java.util.Arrays;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-30 19:01
 * @description: Functions of this class is
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 * 你可以认为每种硬币的数量是无限的。
 *
 * 官方解法（动态规划0-1背包问题）：
 *public class Solution {
 *     public int coinChange(int[] coins, int amount) {
 *         int max = amount + 1;
 *         int[] dp = new int[amount + 1];
 *         Arrays.fill(dp, max);
 *         dp[0] = 0;
 *         for (int i = 1; i <= amount; i++) {
 *             for (int j = 0; j < coins.length; j++) {
 *                 if (coins[j] <= i) { 当前金币的金额小于等于当前所求金额
 *                     dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);情况分为取当前面值硬币/不取当前面值硬币
 *                     取的话，则金币的值为，（当前金额-当前金币数值+（1个金币数））的值
 *                 }
 *             }
 *         }
 *         return dp[amount] > amount ? -1 : dp[amount];
 *判断金额凑不出的小技巧：先初始化DP table各个元素为amount + 1（代表不可能存在的情况）
 * ，在遍历时如果金额凑不出则不更新，于是若最后结果仍然是amount + 1，则表示金额凑不出
 *     }
 * }
 **/
public class No动态规划零钱替换 {
    public static void main(String args[]){
        System.out.println(coinChange(new int[]{186,419,83,408},6249));
    }
    public static int coinChange(int[] coins, int amount) {
        if(amount==0){//如果要求的硬币数为0，则直接返回0
            return amount;
        }
        Arrays.sort(coins);
        int sum=0;//计算每次找到的硬币计算的总金额
        int tot=0;//计算所用的硬币的总数
        int index=coins.length-1;//从硬币金额最大的开始计算
        while (index>=0){
            int coinNum=coins[index];//取出当前的硬币面值
            while (sum<amount){
                sum+=coinNum;//每次都加上这次硬币的总额
                tot++;//硬币数加一
                if(sum==amount){//如果加的过程等于了要求的金额，直接返回
                    return tot;
                }
            }
            //来到这里说明找不到相等的
            while (sum>amount){//减去一枚当前面值的硬币，使得当前面值的硬币尽量多的出现
                tot--;
                sum-=coinNum;
            }
            index--;//对下一个面值的硬币进行计算
        }
        return -1;
    }
}